package com.jake.data_structure_learning.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * copyright (C), 2021, 武汉德辞信息技术有限公司
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/7/6 14:24
 * @description <author>                <time>                  <version>
 * WangXiang               2021/7/6 14:24            1.0.0
 */
public class Solution1 {
    public void bubbleSort(int[] nums) {
        int temp;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = nums[i];
                }
            }
        }
    }

    public void selectSort(int[] nums) {

        int temp;
        for (int i = 0; i < nums.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > nums[index]) {
                    index = j;
                }
            }
            if (index != i) {
                temp = nums[i];
                nums[i] = nums[index];
                nums[index] = nums[i];
            }
        }
    }


    public void insertSort(int[] nums) {
        int temp;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) {
                    temp = nums[j];
                    System.arraycopy(nums, j, nums, j + 1, i - j);
                    nums[i] = temp;
                }
            }
        }
    }

    public void quickSort(int[] nums) {
        this.quickSort(nums, 0, nums.length - 1);
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int base = nums[start];
            int index = start;
            int temp;
            for (int i = start + 1; i <= end; i++) {
                if (nums[i] > base) {
                    temp = nums[index];
                    nums[index] = nums[i];
                    nums[i] = temp;
                    index++;
                }
            }

            int mid = (start + end) / 2;
            this.quickSort(nums, start, mid);
            this.quickSort(nums, mid + 1, end);
        }
    }

    public void mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }

    public void merge(int[] nums, int left, int mid, int right) {
        int _left = left;
        int _right = mid + 1;
        int index = left;

        int[] temp = new int[nums.length];
        while (_left <= mid && _right <= right) {
            if (nums[_left] < nums[_right]) {
                temp[index++] = nums[_left++];
            } else {
                temp[index++] = nums[_right++];
            }
        }

        while (_left <= mid) {
            temp[index++] = nums[_left++];
        }

        while (_right <= right) {
            temp[index++] = nums[_right++];
        }

        for (int i = left; i < right; i++) {
            nums[i] = temp[i];
        }
    }

    //n u m s 1 = [ 1 , 2 , 2 , 1 ] , n u m s 2 = [ 2 , 2 ]
    public List<Integer> intersect(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;
        List<Integer> list = new ArrayList<>();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] > nums2[j]) {
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        return list;
    }

    public int characterReplacement(String s, int k) {
        char[] chars = s.toCharArray();
        int left = 0;
        int right = 0;
        int maxCount = 0;
        for (; right < chars.length; right++) {
            maxCount = Math.max(maxCount, this.maxSameCount(chars, left, right));
        }
        return 0;
    }

    public int maxSameCount(char[] chars, int start, int end) {
        int count = 0;
        for (int i = start; i <= end; i++) {
//            if (chars[i] == c) {
//                count++;
//            }
        }
        return count;
    }

    public static void findMin(int[] nums) {
        int left = 0;
        int right = 0;

        int maxSum = 0;
        while (right < nums.length) {

            while (left<=right) {
                maxSum = Math.max(maxSum, sum(nums, left, right));
                left++;
            }
            right++;
        }
        System.out.println(left);
        System.out.println(right);
        System.out.println(maxSum);
    }

    public static int sum(int[] nums, int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}
